1. Field of the Invention
The present invention relates to a system, which can relax constraints in, e.g., a scheduling system, a design assist system, an action planning system, and the like, and can specify or limit the values that variables can assume so that all the constraints are satisfied.
2. Description of the Related Art
In general, a constraint satisfaction system for specifying or limiting the values that variables can assume to satisfy constraints upon planning of some given schedules suffers from the following technical difficulty. That is, when a solution that satisfies all the constraints is to be obtained, some constraints are often too strict for the system to obtain such a solution. Even if a solution that satisfies all the constraints is present, in some cases, a set of final solutions to be searched are extremely limited, and a vast space candidate solutions must be searched. As a result, a long calculation time is required.
Some of these constraints need not always be strictly satisfied according to conditions. For example, in a production scheduling problem, although constraints associated with the way of use of production machines are often given, the way of use of machines is normally flexible to some extent, and can be changed more or less depending on conditions. In this manner, in an actual constraint satisfaction problem, constraints can be relaxed to widen a "solution space" or "a set of candidate solutions".
As an early technique for solving a constraint satisfaction problem, an approach based on the operations research (to be referred to as the "OR" hereinafter) has been popular.
In the approach based on the OR, constraints are "formulated" by mathematical programming represented by linear programming or integer programming. In the method using the mathematical programming, constraints must be fixed upon formulation, and cannot be changed in a process of obtaining a solution. Although an optimal solution can be obtained, the types of constraints are limited. For example, in the linear programming, constraints must be expressed in the forms of equations and inequalities of linear combinations of variables. In the integer programming, variables themselves must be integers. Therefore, the approach based on the OR is not always best suited for general "Constraint Satisfaction Problems" (normally abbreviated to as a CAP), except for "problems for which constraints are accurately described, and which require a strict optimal solution".
An approach based on an expert system adopting an artificial intelligence (to be referred to as AI hereinafter) technique is introduced for the purpose of compensating for the drawbacks of the approach based on OR. In the approach based on AI, a generate-and-test method for repeating "generation of a candidate solution" and "check of constraint satisfaction" on the basis of the search in the space of possible solutions is the mainstream. This method is suitable for constraint satisfaction problems since "solutions that satisfy constraints can be obtained without obtaining an optimal solution". "Constraints" are acquired from experts of the corresponding fields upon construction of the system (called knowledge acquisition), and are built in a knowledge base.
In the constraint satisfaction system based on the expert system, attempts have been made to flexibly cope with constraint relaxation. For example, in a certain system, constraints are classified into some classes according to their possibility of relaxation. When the necessity of constraint relaxation occurs, relaxation is performed from constraints in the relaxation possible class. However, in this system, whether or not constraint relaxation is possible must be decided upon construction of the system, and such knowledge must be acquired from the experts of the corresponding fields. In addition, the expert must present this decision knowledge while assuming "situations in which constraints are violated", and correct knowledge about possibility of relaxation cannot always be obtained. Even when constraint relaxation information becomes necessary during solving of a constraint satisfaction problem, it cannot be dynamically added.